package com.leetcode.array;

/**
 * 209. 长度最小的子数组
 * 给定一个含有n个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，
 * 并返回其长度。如果不存在符合条件的子数组，返回 0 。
 * 示例 1：
 * 输入：target = 7, nums = [2,3,1,2,4,3]
 * 输出：2
 * 解释：子数组[4,3]是该条件下的长度最小的子数组。
 * 示例 2：
 * 输入：target = 4, nums = [1,4,4]
 * 输出：1
 * 示例 3：
 * 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
 * 输出：0
 * 提示：
 * 1 <= target <= 109
 * 1 <= nums.length <= 105
 * 1 <= nums[i] <= 105
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author ymy
 * @date 2021年12月08日 10:56
 */
class Code209 {
    public static void main(String[] args) {
        Code209 code = new Code209();
        int[] nums = new int[]{1,4,4};
        int k = code.minSubArrayLen(4, nums);
        System.out.println(k);
    }
    public int minSubArrayLen1(int target, int[] nums) {
        int count = 0;
        int p = 0;
        int q = 1;
        int min = Integer.MAX_VALUE;
        boolean flag = false;
        for(int i = 0;i< nums.length;i++){
            count += nums[i];
            if(count>=target){
                q = i;
                if(i == 0){
                    return 1;
                }
                flag = true;
                break;
            }
        }
        if(!flag){
            return 0;
        }
        while (p<nums.length){
            if(count >= target){
                int len = q-p+1;
                min = len < min ? len : min;
                count -= nums[p];
                p++;
            }else{
                if(q + 1 < nums.length){
                    q++;
                    count += nums[q];
                }else {
                    break;
                }
            }

        }
        return min;
    }
    /**
     * 精简滑动窗口算法
     * @author ymy
     * @date 2021/12/8 11:42
     * @param target
     * @param nums
     * @return int
     */
    public int minSubArrayLen(int target, int[] nums) {
        int min = Integer.MAX_VALUE;
        int p = 0;
        int count = 0;
        for(int i = 0;i<nums.length;i++){
            count += nums[i];
            while (count >= target){
                int len = i-p+1;
                min = len < min ? len : min;
                count -= nums[p];
                p++;
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}
